\documentclass{iccmemoria}
\usepackage[latin1]{inputenc}
\usepackage[spanish]{babel}
\usepackage{epsfig}
\usepackage{colortbl}
\RequirePackage{graphicx}
\DeclareGraphicsExtensions{.pdf,.png,.jpg}

\titulo{Estudio de rendimiento de aplicaciones paralelas para arquitecturas de tipo GPU}
\author{Marcelo Aaron Espina Rosas}
\supervisor{Matt Bardeen}
\informantes
	{Federico Meza}
	{}
\adicional{}
\date{Mayo, 2010}

\begin{document}

\maketitle

\tableofcontents

\chapter{Introducci\'{o}n}
  
Durante esta memoria se procurara evaluar un posible nuevo paradigma para los problemas de de Alto Rendimiento Computacional, intentando llevarlos a cabo sobre un tarjeta de vdeo de la nueva generaci\'{o}n de tarjetas de Nvidia.
  \par
  Es necesario dejar en claro que en esta memoria no buscamos desarrollar ning\'{u}n tipo problema concerniente al aspecto gr\'{a}fico.
  \par
  Para lograr el cometido de esta memoria hemos de analizaremos a fundo el paradigma de la computaci\'{o}n paralela, intentando a groso modo descifrar algunos de los problemas y las limitaciones que en este se presentan, as\'{\i} como tambi\'{e}n analizar sus posibles soluciones, para en una \'{u}ltima etapa intentar comprender la forma en que se puede evaluar la efectividad de cada soluci\'{o}n.
  \par
  Luego de esto analizaremos las caracter\'{\i}sticas m\'{a}s relevantes de las tarjetas de v\'{\i}deo en cuesti\'{o}n, intentando comprender sus capacidades de computo, para esto \'{u}ltimo, se analizaran algunos de los documentos de los proyectos m\'{a}s relevantes y concernientes al tema que buscamos tratar.
  \par
  Se analizaran algunos de los proyectos de computaci\'{o}n paralela, que no sean implementados necesariamente en la unidad de procesamiento central, sino en alguna otra estructura, como lo puede ser la Play Station 2.
  \par
  Finalizando nuestro recorrido se proceder\'{a} a evaluar algunos de los problema de alto rendimiento computacional que son factibles de llevar a cabo sobre la nueva generaci\'{o}n de tarjetas de v\'{\i}deo, luego de esto se proceder\'{a} a implementar la soluci\'{o}n para el problema de HPC seleccionado, y en una \'{u}ltima etapa se evaluaran los resultados obtenidos, demostrando que tan cierto o valido es este nuevo paradigma.
  \par
  Finalmente se realizara la elecci\'{o}n de un problema a ser analizado con grado mayor de detalle, intentando lograr mejorar en alguna medida los resultados de las implementaciones anteriores, intentando establecer alg\'{u}n tipo de referencia para el problema, se procurar mejorar alguna implementaci\'{o}n del pasado, como lo puede ser una implementaci\'{o}n en alguna maquina con caracter\'{\i}sticas de alto procesamiento de datos.
\chapter{El Problema}
  En esta secci\'{o}n se describe el problema que se tratara en esta memoria, y de como se encuentra contextuado en el mundo de hoy en d\'{\i}a. Se habla adem\'{a}s de las expectativas que se tiene del proyecto y de las cosas que se espera realizar durante este.
\section{Introducci\'{o}n}
  En la actualidad existe muchos y variados problemas que requieren de un alto grado de procesamiento de datos \'{o} alto rendimiento computacional, cada uno de ellos con sus propias limitantes y variantes. Pero en la actualidad con el creciente desarrollo de los equipos computacionales, con la constante incorporaci\'{o}n de nuevas t\'{e}cnicas computacionales, matem\'{a}ticas, heur\'{\i}sticas, dentro de muchas otras cosas, se ha vuelto m\'{a}s que una tarea un desaf\'{\i}o, romper las barreras de tiempo que hoy en d\'{\i}a presentamos, si bien, gran parte de lo anterior a convulsionado a que se logren mejores respuestas en menores tiempos, en muchos casos la misi\'{o}n aun estas lejos de cumplirse, es por esto que se siguen explorando nuevas formas, t\'{e}cnicas y tecnolog\'{\i}as para lograr resolver estos problemas.
  \par
  En esta memoria se pretende explorar una naciente tecnolog\'{\i}a, mediante la cual atacar estos problemas.
\section{Descripci\'{o}n del Problema}
  Esta memoria procurara evaluar un posible nuevo paradigma para los problemas de Alto Rendimiento Computacional, intentando llevar los problemas a las unidades de
 procesamiento gr\'{a}fico de computo de prop\'{o}sito general de alguna de las tarjetas v\'{\i}deo de nueva generaci\'{o}n de la familia Nvidia.
  \par
  La idea es explotar el paralelismo con el que cuentan estas nuevas tarjetas de v\'{\i}deo, intentando resolver algunos de los problemas alto desempe\~{n}o computacional sobre la tarjeta en cuesti\'{o}n, intentando demostrar a modo de prueba de concepto el rendimiento de una aplicaci\'{o}n de altamente demandante de rescursos y calculos computacionales sobre la unidad de procesamiento central apoyada por la unidad de procesamiento gr\'{a}fico.
\section{Descripci\'{o}n del Contexto}
  En la actualidad muchas de las organizaciones, dedican gran parte del tiempo a la toma de decisiones, 
pero muchas veces esta decisiones no son del todo sencilla puesto que estas implican analizar una gran 
cantidad de informaci\'{o}n en muy poco tiempo, por ello es que requieren alg\'{u}n tipo de modelos o soluci\'{o}n 
computacional, el problema se presenta cuando estos modelos o bien no entregan la soluci\'{o}n en el tiempo 
que se requiere, \'{o} porque no existe un modelo o sistema lo suficientemente capaz de brindar estas soluciones \cite{Barnett2007}.
  \par
  Cualquiera sea el caso que se presente, para la organizaci\'{o}n esto presenta perdidas tremendas, 
no solo en t\'{e}rminos monetarios sino que tambi\'{e}n en gasto innecesario de tiempo, 
deterioro de la imagen comercial que se ve afectada, lo que en el fondo de una forma u otra se traduce en una perdida monetaria. 
He aqu\'{\i} la importancia de explotar nuevas tecnolog\'{\i}as que permitan obtener nuevas y mejores soluciones.
  \par
  Actualmente uno de los campos m\'{a}s explorados, que involucra la resoluci\'{o}n de este tipo de dilemas, 
es el de la computaci\'{o}n paralela y/\'{o} distribuida, 
mediante este paradigma de la computaci\'{o}n se ha logrado conseguir nuevas y mejores soluciones \cite{Barnett2007}, 
y en algunos casos se han logrado resultados que antes se pensaban imposibles. 
No obstante, con el uso de esta herramientas de computaci\'{o}n, no se puede asegurar obtener una soluci\'{o}n del todo satisfactoria, 
esto debido a que este paradigma presenta algunos inconvenientes y limitaciones practicas, 
ya que la arquitectura sobre la que trabajan no es la adecuada.
  \par
  Hoy en d\'{\i}a existen muchas otras t\'{e}cnicas para intentar resolver este tipo de problemas,
ya sea mediante Inteligencia Artificial, Cluster Computacionales, la antes mencionada Computaci\'{o}n Paralela y/\'{o} Distribuida, 
el dilema es que estas t\'{e}cnicas no son del todo efectivas en su totalidad, 
pero con el creciente desarrollo de tarjetas de v\'{\i}deo se ha comenzado a descubrir un nuevo paradigma para resolver estos problemas, 
dado que las nuevas tarjetas han aumentado sus capacidades de procesamiento, 
es que hoy en d\'{\i}a estas ya no son necesariamente exclusivas para el procesamiento de gr\'{a}ficos, 
ya tenemos tarjetas de v\'{\i}deo de prop\'{o}sito general, vale decir, y
a no son necesariamente exclusivas para el concerniente al procesamiento de gr\'{a}ficos (como imagenes), 
ahora pueden realizar alguna de las funciones que normalmente realiza la unidad de procesamiento central, 
y dado su dise\~{n}o sofisticado, dedicado para trabajar simult\'{a}neamente sobre diversas tareas en un mismo intervalo de tiempo, 
es que se nace la duda de si podremos resolver alg\'{u}n problema de alto desempe\~{n}o computacional, 
sobre alguna de estas tarjetas de v\'{\i}deo de la Familia de Nvidia \cite{NvidiaCorporation.2010},\cite{NvidiaCorporation.2009},\cite{Glaskowsky2009}.
\section{Objetivos}
  En esta secci\'{o}n se describir\'{a}n los objetivos que se buscaran en esta memoria. 
\subsection{Objetivo General}
  Durante este proyecto se pretenden obtener conocimiento de dos grandes temas, por una lado, 
se pretende comprender la arquitectura de las tarjetas de v\'{\i}deo de la familia Nvidia,  
incluyendo su modelo y API de programaci\'{o}n, sin dejar de lado de las limitaciones y ventajas de la misma, 
y en un segundo plano comprender el paradigma de la computaci\'{o}n paralela, 
sus limitaciones as\'{\i} como alguno de los casos mayormente emblem\'{a}ticos del tema en si 
y la forma en que cada problema puede ser abordado. 
Para con estos dos grandes temas lograr el conocimiento necesario que permita lograr identificar y 
dise\~{n}ar aplicaciones paralelas que trabajen sobre estas tarjetas, 
demostrando a modo de prueba de concepto el rendimiento de una aplicaci\'{o}n de de alto desempe\~{n}o sobre estas tarjeta de v\'{\i}deo.
\subsection{Objetivos Espec\'{\i}ficos}
  Los objetivos espec\'{\i}ficos que se buscan realizar durante este proyecto son los siguientes:
  
\begin{itemize}
\item Conocer y comprender arquitectura de las tarjetas de v\'{\i}deo.
\item Conocer y comprender API de programaci\'{o}n de las tarjetas de v\'{\i}deo
\item Conocer y comprender Modelo de Programaci\'{o}n de las tarjetas de v\'{\i}deo
\item Conocer y comprender paradigma de la computaci\'{o}n paralela.
\item Estudiar problemas tradicionales que podr\'{\i}an resolverse mediante paralelismo.
\item Estudiar problemas \'{o} proyectos sobre las tarjetas de v\'{\i}deo ya resueltos \'{o} en proceso de desarrollo.
\item Escribir programas peque\~{n}os a modo de prueba en las tarjetas de v\'{\i}deo.
\item Resolver un problema de alto desempe\~{n}o computacional sobre las tarjetas de v\'{\i}deo.
\item Evaluar la soluci\'{o}n obtenida respecto de implementaciones tradicionales.
\end{itemize}

\section{Resumen}
  Durante este capitulo se expuso el tema de la presente memoria, 
se dio a conocer la problem\'{a}tica que re\'{u}ne y junto con esto el contexto del mismo, 
as\'{\i} como tambi\'{e}n una pincelada de las formas en que actualmente se pude atacar nuestro problema, 
se debe mencionar que este tema se tratar\'{a} con mayor detalle en el siguiente capitulo. 
Adem\'{a}s se comentaron los objetivos que se perseguir\'{a}n de ahora en m\'{a}s, 
esperando con estos lograr llevar a delante este proyecto.
\par
  En el siguiente capitulo se hablara con mayor detalle de algunas de las t\'{e}cnicas que actualmente 
se utilizan para resolver problemas de alto desempe\~{n}o computacional, 
se habla adem\'{a}s de aquellos aspectos que el lector deber\'{\i}a conocer antes de continuar con la lectura.

\chapter{Marco Te\'{o}rico}

\section{Introducci\'{o}n}
  Esta memoria esta fundamentada en la inquietud naciente, 
acerca del creciente desarrollo de las unidades gr\'{a}ficas de procesamiento  
y de sus constantes mejoras,  llev\'{a}ndolas a convertirse en unidades de procesamiento gr\'{a}fico de prop\'{o}sito general, 
y de su prometedor poder para realizar tareas de manera simultanea, 
lo que nos plantea la inquietud de resolver problemas de un alto nivel de procesamiento sobre una de estas tarjetas, 
intentando explotar al m\'{a}ximo el paradigma de la computaci\'{o}n paralela.
  \par
  Este capitulo se enfoca en entregar al lector aquellos conocimientos que le son necesarios para la comprensi\'{o}n de esta memoria.
  \par
  A continuaci\'{o}n hemos de discutir lo que com\'{u}nmente se conoce como problemas de alto desempe\~{n}o computacional, 
a continuaci\'{o}n discutiremos algunas de la t\'{e}cnicas que hoy en d\'{\i}a se usan para resolver estos problemas, 
para luego proceder a analizar la evoluci\'{o}n de las unidades de procesamiento central y unidades de procesamiento gr\'{a}fico, 
terminando por hablar de los problemas que hoy en d\'{\i}a se resuelven mediante el uso de tarjetas de v\'{\i}deo, 
as\'{\i} como de alguna otra implementaci\'{o}n que se asemeje a lo que se busca con esta memoria.
\section{Problemas de Alto Desempe\~{n}o Computacional}
  Los problemas de alto desempe\~{n}o computacional desde ahora HPC (del ingles High Performance Computing), 
son aquellos problemas altamente demandantes de gran cantidad de computo computacional y en algunos casos, 
requerimientos de gran capacidad de recursos computacionales, com\'{u}nmente asociado con s\'{u}per computadores, 
que se caracterizan por su alto gran grado de procesamiento de datos.
  \par
  Los problemas de HPC, requiere de equipos especializados, tales como las supercomputadores \'{o} los cluster computacionales, 
pero adem\'{a}s de estos se puede encontrar buenas soluciones mediante el uso por ejemplo de computaci\'{o}n paralela, 
en la que una sola maquina logre procesar m\'{a}s de una instrucci\'{o}n simult\'{a}neamente, \'{o} de computaci\'{o}n distribuida, 
en la que muchas maquinas unidas mediante un bus para los datos, logran resolver los problemas en conjunto.
  \par
  Un t\'{\i}pico problema de de HPC, consiste en recorrer completamente una serie de nodos interconectados entre s\'{\i}, 
visitando cada nodo una sola vez y volviendo al nodo de partida, minimizando el costo o camino total recorrido al visitar los nodos.
  \par
  En t\'{e}rminos de restricciones el problema es bastante sencillo, 
pero su complejidad crece exponencialmente conforme se agregan nodos a la secuencia, 
lo que implica un incremento exponencial en el tiempo necesario para obtener una soluci\'{o}n, 
por tanto las instancias del problema a resolver tienen una cota en cuanto a t\'{e}rminos de tiempo de ejecuci\'{o}n, 
ya que no queremos tener que esperar mucho tiempo para obtener una respuesta a nuestro problema, 
esto implica que las t\'{e}cnicas de resoluci\'{o}n no son del todo efectivas dado las restricciones del problema.
  \par
  Es aqu\'{\i} que nacen nuevas y variadas t\'{e}cnicas para la resoluci\'{o}n de este 
y muchos otros problemas con vol\'{u}menes de informaci\'{o}n iguales o superiores al del problema descrito, 
dentro de las cuales podemos mencionar cluster, computaci\'{o}n paralela y distribuida, computaci\'{o}n grid, 
las cuales se explicitaran a continuaci\'{eo}n.

\section{Computaci\'{o}n Paralela y Distribuida}
  Este paradigma, se basa en el trabajo en equipo, 
de esta forma un problema es subdividido en problemas a\'{u}n m\'{a}s peque\~{n}os, 
que deben resolverse para lograr en un conjunto resolver un problema mayor, 
cada una de estas partes es distribuido a cada una de las unidades de procesamiento de las que se disponga. 
Los problemas por lo general son divididos de modo tal, 
que cada una de la unidades de procesamiento resuelvan problemas el mismo subproblema, 
pero sobre datos totalmente independientes entre si, de este modo se maximiza el trabajo en paralelo.
  \par
  Existen dos enfoques para establecer una sistema paralelo, 
primero tenemos los multiprocesadores, en esto los procesos se comunican a trav\'{e}s de lectura y escritura de memoria compartida, 
mediante este m\'{e}todo los programas pueden establecer un sistema de comunicaci\'{o}n estable, 
b\'{a}sicamente al hablar de un multiprocesador nos referimos a un computador con m\'{a}s de una unidad de procesamiento (dual-core, quad-core). 
En segundo lugar tenemos los multicomputadores, en los cuales cada uno de los proceso tiene su memoria individual, 
para estos la comunicaci\'{o}n se establece mediante env\'{\i}o de mensajes 
por medio de la red que los mantiene interconectados \cite{Campos2002},\cite{DeGijon}.
  \par
  El principal problema que presentan los multiprocesadores, 
es que no es posible agregar procesadores indefinidamente, 
existe un limite, esto porque llegado su punto la comunicaci\'{o}n se satura, 
adem\'{a}s como bien se explica en\cite{Celis2004}, en base a lo que afirmo Gordon Moore en 1965, 
en que la tecnolog\'{\i}a tendr\'{\i}a un gran futuro, 
prediciendo de forma acertada el crecimiento de forma exponencial de los avances de la tecnolog\'{\i}a, 
a\~{n}os mas tarde cambio su primera ley afirmando que el ritmo de crecimiento bajar\'{\i}a a la mitad, mas aun, 
el propio Moore estableci\'{o} fecha de caducidad de su propia ley (entre de los a\~{n}os 2017 y 2023), 
afirmando que nuevas tecnolog\'{\i}as aparcer\'{\i}a para ocupar el lugar de la actual. 
En tanto que la principal desventaja que presenta los multicomputadores es que dado que para su comunicaci\'{o}n 
utilizan un medio f\'{\i}sico como una red, este medio muchas veces puede verse saturado por variables externas, 
adem\'{a}s este no es del todo eficiente, por tanto, retrasa la ejecuci\'{o}n de los programas al agregar la latencia de la red misma.
  \par
  Para lograr realizar un programa que trabaje en paralelo, 
es necesario comprender como funciona, por ejemplo, 
en la imagen siguiente se ejemplifica el fundamento de la computaci\'{o}n paralela, 
en esta se tiene un programa el que corresponde al de la parte superior, 
en este se debe realizar trabajo de manera secuencial, (color azul), 
pero adem\'{a}s se ha identificado que este necesita realizar el mismo proceso de manera reiterada (color rojo), 
en donde el largo corresponde al tiempo que la tarea requiere para ser ejecutada.
  \par
  \begin{center}
  \includegraphics{imgSalida/secuencial.eps}
  \end{center}
  \par
  Podr\'{\i}amos pensar que el trabajo total se podr\'{\i}a dividir de modo tal que todas las unidades de procesamiento 
realicen una parte de la tarea, de este modo estamos paralelizando el programa, 
en la imagen siguiente se muestra el efecto de paralelizar el mismo programa. 
En la parte superior tenemos el mismo programa en secuencial, y mas abajo se encuentra el programa paralelizado, 
como podemos observar el tiempo necesario para ejecutar completamente el mismo programa se reduce de manera considerable.
  \par
  \begin{center}
  \includegraphics{imgSalida/paralelo.eps}
  \end{center}
  \par
  Ahora nos surge la duda de porque no se paralelizan todos los algoritmos, y el problema surge, 
ya que no todos los programas puedes ser paralelizados, m\'{a}s aun, 
existen algoritmos que el solo echo  de paralelizarlos los puede volver mas lentos, 
esto porque depende directamente de la fracci\'{o}n del programa en cuesti\'{o}n que puede ser ejecutado en paralelo, 
si la fracci\'{o}n es demasiado peque\~{n}a quiz\'{a} el  beneficio no sea suficiente como para que amerite el costo del cambio, 
en fin son variadas las variables que influyen a la hora de determinar si se puede o no paralelizar un programa \cite{DeGijon}, \cite{Nunez2002}, 
adem\'{a}s debemos recordar que nos enfrentamos a leyes como la de Amdahal, 
en la que se establece que existe una limite en cuanto m\'{a}s r\'{a}pido puede ser un programa paralelizado \cite{Lopera2009} y la ley de Gustafson, 
que nos da un pronostico un tanto mas auspicioso que la ley de Amdahal, 
en esta se establece que mientras mas grandes son los problemas, mayor es la posibilidad de paralelizarlo, 
ley que no deja de ser menor, dado nuestras pretensiones de paralelizar problemas de HPC cada vez mas grandes 
y por consiguiente complejos.
  \par
  Mediante el paradigma de la computaci\'{o}n paralela y distribuida nos es posible resolver instancias de problemas de HPC mucho mayores, 
pero hemos de mencionar una gran desventaja para la cual no se tiene soluci\'{o}n sobre las arquitecturas de Von Neuman 
de los actuales computadores, y es dado a que no est\'{a}n pensadas para procesos paralelos, vale decir, 
las unidades de procesamiento de los computadores modernos no se encuentran orientado para trabajar simult\'{a}neamente, sino, 
en de manera secuencial (un programa a la vez).
  \par
  Dentro de esta categor\'{\i}a tenemos uno de los proyectos mas demandantes de la \'{u}ltima \'{e}poca, Folding Home, 
el cual es una aplicaci\'{o}n distribuida para modelar el plegamiento de las prote\'{\i}nas. 
Para modelar el plegamiento de la prote\'{\i}nas en un sistema como un cluster de programaci\'{o}n mediante computaci\'{o}n paralela, 
se tardar\'{\i}a alrededor de 30 a\~{n}os de CPU para simular todo el plegamiento, 
por tanto la estrategia que se opto fue la de la de centralizar la coordinaci\'{o}n en una sola maquina que har\'{a} de servidora, 
permitiendo que cualquier computador pueda ser parte de la soluci\'{o}n, de acuerdo a esto, la idea es que un equipo terminal,
como lo podr\'{\i}a ser la t\'{\i}pica computadora que todos utilizamos, pueda ayudar a resolver una porci\'{o}n del problema, as\'{\i}, 
la maquina terminal se sincroniza con la maquina servidora, pidi\'{e}ndole alguna tarea para realizar, 
entregando sus resultados una vez que lo tenga resuelto \cite{Barnett2007}.
  \par
  Hoy en d\'{\i}a estamos a puertas del nacimiento de los auto-denominados chips de quinta generaci\'{o}n,
con el lanzamiento de la nueva generaci\'{o}n de tarjetas de v\'{\i}deo por parte de Nvidia, 
estas a diferencia de los procesadores comunes \'{o} CPU est\'{a}n pensados para desarrollar muchas tareas en paralelo 
con un muy bajo costo computacional, hemos de echar un vistazo mas a fondo a este tema mas adelante.
  \par
\section{La Unidades de Procesamiento Central}
  La funci\'{o}n principal de las desde ahora CPU (del ingles Central Processing Unit), 
es ejecutar una seria de instrucciones almacenadas, llamadas programas. 
La CPU puede realizar cuatro pasos leer, decodificar, ejecutar y escribir (del ingles Fetch, Decode, Execute, Writeback), 
por lo tanto para que una CPU ejecute un programa, esta debe leer las instrucci\'{o}n del programa que se quiere ejecutar, 
luego de esto la instrucci\'{o}n que se encuentra almacenada de forma binaria (en t\'{e}rminos de 0 y1), 
es necesario que se decodifique para que el CPU logre entender que es lo que se debe realizar, 
algunas veces estas instrucciones requieres por ejemplo de algunas otras entradas, 
(por ejemplo realizar la suma de un par de n\'{u}meros), para esto se requiere la lectura de estos ?gregistros?h, 
en otros casos no es requerido nuevas lecturas, al cavo de finalizada la lectura y la decodificaci\'{o}n, 
la instrucciones pasa a ser ejecutada en la unidad aritm\'{e}tico l\'{o}gica desde ahora ALU, 
al final lo \'{u}nico que queda es guardar el resultado de la operaci\'{o}n en alg\'{u}n lugar de la memoria.
  \par
  \begin{center}
  \includegraphics{imgSalida/diagramaCPU.eps}
  \end{center}
  \par
  El principal problema que presenta la CPU es que esta dispuesta sobre un \'{u}nico BUS 
que interconecta los componentes de la arquitectura, 
mediante este BUS se realizan las operaciones de lectura y escritura de la memoria, 
por tanto solo se puede realizar una operaci\'{o}n a la vez ya sea lectura o escritura, 
si bien hoy en d\'{\i}a, el ancho de banda de los buses el grande, 
logrando una mayor cantidad de operaciones sobre la memoria en un menor tiempo, 
si quisi\'{e}ramos realizar alguna operaci\'{o}n altamente demandante de recursos en memoria, 
como lo puede los programas que trabajan en paralelo, 
este bus se puede convertir en un cuello de botella que limitar\'{\i}a la eficiencia de los programas, 
y ese echo es muy com\'{u}n a la hora de realizar problemas de HPC, donde podemos encontrar algoritmos altamente paralelizables, 
pero por este tipo de limitaci\'{o}n no es factible lograr una soluci\'{o}n \'{o}ptima.
  \par
  La alternativa que se quiere explorar en esta memoria consite en utilizar las nuevas tarjetas de v\'{\i}deo de Nvidia, 
las cuales prometen ser altamente paralelizables, adem\'{a}s de contar con muchas unidades de procesamiento a nivel de shader 
que ya son de prop\'{o}sito general.

\section{La Unidad de Procesamiento Gr\'{a}fico}
  La unidad de procesamiento gr\'{a}fico desde ahora GPU, 
es un procesador dedicado a procesar gr\'{a}ficos es decir todo aquello relacionado a las im\'{a}genes. 
Hoy en d\'{\i}a las GPU ya no son necesariamente exclusivas para el procesamiento gr\'{a}fico, 
alguna de las GPU constan de unidades de procesamiento que soportan c\'{a}lculos de prop\'{o}sito general, 
vale decir son unidades de procesamiento gr\'{a}fico de prop\'{o}sito general desde ahora GPGPU 
(del ingles General Purpose Computing on Graphics Processing Unit), 
que en el fondo busca aprovechar las capacidades de computo de las GPU para lograr mejoras en los programas, 
al liberar de trabajo a la CPU \cite{NvidiaCorporation.2009}.
  \par
  La siguiente imagen muestra una comparaci\'{o}n del aumento en capacidades de procesamiento, 
tanto en las CPU como en las GPU, 
en esta podemos ver que las GPU han logrado un crecimiento semejante a una curva exponencial 
en tanto que las CPU solo lograron un crecimiento lineal. 
Esto nos muestra la importancia que presentan las GPU dentro de campo de la computaci\'{o}n.
  \par
  \begin{center}
  \includegraphics{imgSalida/graficoCrecimiento4.eps}
  \end{center}
  \par
\section{Trabajos Actuales}
  Actualmente existen muchos trabajos relacionados con las tarjetas de v\'{\i}deo de la familia Nvidia, 
que han logrado sacar provecho de las caracter\'{\i}sticas de las tarjeta de video de la familia Nvidia, 
a continuaci\'{o}n se presenta una tabla con las mas significativas aplicaciones y sus respectivos incrementos de velocidad.
  \par
\begin{center}
  \begin{tabular}{|l|l|} \hline
  GPU computing applications developed on the CUDA architecture & Speed Up \\ \hline \hline
  Fast implementation of Wyner-Ziv Video codec using GPGPU & 20X \\ \hline
  NeuroSolutions CUDA Add-on & 50X \\ \hline
  Bayesian Real-Time Perception Algorithms on GPU & 30.000X \\ \hline
  A Work-Efficient GPU Algorithm for Level Set Segmentation & 14X \\ \hline
  Performance and Scalability of GPU-Based Convolutional Neural Networks & 24X \\ \hline
  AntiPlanet Reflections & 30X \\ \hline
  High-performance cone beam reconstruction using CUDA compatible GPUs & 24X \\ \hline
  Iterative induced dipoles computation for molecular mechanics on GPUs & 21X \\ \hline
  Exploring NVIDIA-CUDA for video coding & 100X \\ \hline
  Palo GPU Business Intelligence & 40X \\ \hline
  Best-effort semantic document search on GPUs  & 14X \\ \hline
  Fast Image Blurring with CUDA & 300X \\ \hline
  Accelerating SQL Database Operations on a GPU with CUDA & 70X \\ \hline
  \end{tabular}
\end{center}
 

 \par
  Como podemos observar, los problemas que mayormente logran los resultados m\'{a}s significativos 
son las que se encuentran relacionadas con el procesamiento gr\'{a}fico, pero aun as\'{\i}, 
es interesante hacer notar la ultima fila, 
en donde se encuentra una implementaci\'{o}n de un problema que no se encuentra relacionado con el procesamiento gr\'{a}fico,
y aun as\'{\i} lograron un considerable incremento en la velocidad, este es un echo un tanto alentador, 
dadas las caracter\'{\i}sticas de este problema, hemos de centrar nuestro estudio en este.
\section{Resumen}
  En este capitulo se hablo de los aspectos t\'{e}cnicos m\'{a}s relevantes, 
dentro del \'{a}rea de estudio que conforman los fundamentos te\'{o}ricos y pr\'{a}cticos 
para los que se pretende realizar en esta memoria. 
La computaci\'{o}n paralela es uno de los aspectos fundamentales, para las pretensiones de esta, 
ya que en base a esta es que se pretende implementar una soluci\'{o}n 
para alg\'{u}n problema que requiera una alto rendimiento computacional, 
dadas las caracter\'{\i}sticas de las nuevas tarjetas de v\'{\i}deo de la familia Nvidia. 
En este se esboza algunos de los problemas b\'{a}sicos a los que hemos de enfrentar 
cuando comencemos a desarrollar nuestra soluc\'{o}n.

\chapter{Metodolog\'{\i}a}

\section{Introducci\'{o}n}

\section{Metodolog\'{\i}a de programaci\'{o}n paralela}
  En este capitulo se describe la metodolog\'{\i}a que se debe llevar acabo para realizar programaci\'{o}n paralela o distribuida. 
Mediante este se pretende dar a conocer los problemas que este paradigma presenta.
  \par
  La concepci\'{o}n de una implementaci\'{o}n de un problema paralelo, as\'{\i} como de su soluci\'{o}n e implementaci\'{o}n, 
presenta a lo menos 2 etapas claramente marcadas, las cuales son Descomposici\'{o}n y Asignaci\'{o}n.
  \par 
    \begin{center}
      \includegraphics{imgSalida/metodologiaParalelo.eps}
    \end{center}
  \par
  Cada una de estas atiende sus propias disyuntivas, las cuales se describen a continuaci\'{o}n.

\subsection{Descomposici\'{o}n}
  La etapa de descomposici\'{o}n comprende desde que se concibe el problema como un problema de HPC, 
altamente paralelizable, \'{o} con algunas caracter\'{\i}sticas m\'{\i}nimas que nos indique que la factibilidad de la soluci\'{o}n por desarrollar.
La descomposici\'{o}n implica como su nombre lo indica descomponer el problema en cuesti\'{o}n en peque\~{n}os subproblemas completos, 
vale decir, que ser\'{a}n independientes del resto, 
este proceso es recursivo y depender\'{a} exclusivamente del grado de granularidad que se desee \'{o} necesite logra.
  \par
  Si bien son varios los niveles de granularidad de los que podemos hacer referencia,
solo dos de ellos han de ser nuestro foco de atenci\'{o}n esto debido a la arquitectura en la que el problema se resolver\'{a}.
  \par
  Mediante la descomposici\'{o}n se obtiene un conjunto de tareas, 
junto con una descripci\'{o}n de su estructura de comunicaci\'{o}n que exhibe un grado de concurrencia alto.
  \par
  Al descomponer problemas de HPC, hemos de considerar lo siguiente:
  \begin{itemize}
  \item M\'{a}ximo grado de concurrencia: Mayor n\'{u}mero de tareas cuya ejecuci\'{o}n se podr\'{\i}a realizar al mismo tiempo
  \item Grado medio de concurrencia: N\'{u}mero medio de tareas que se podr\'{\i}a ejecutar en paralelo.
  \end{itemize}
  \par
  Estas caracter\'{\i}sticas est\'{a}n netamente relacionadas con las capacidades de tarjeta de v\'{\i}deo en cuesti\'{o}n, 
las cuales se presentan a continuaci\'{o}n.
\par
\begin{table}[!hbt]
\begin{center}
\begin{tabular}{| l | c | c | c | c | c |}
   \hline
   & \multicolumn{5}{c|}{Capacidad inform\'{a}tica}\\
  \hline
  Especificaci\'{o}n T\'{e}cnica & 1.0 & 1.1 & 1.2 & 1.3 & 2.0\\
  \hline
  M\'{a}xima dimensi\'{o}n de un grid de bloques de hilos & \multicolumn{5}{c|}{65535}\\
  \hline
  M\'{a}ximo n\'{u}mero de hilos por bloque & \multicolumn{4}{c|}{512} & \multicolumn{1}{c|}{1024}\\
  \hline
  M\'{a}ximas dimensiones X e Y de un bloque & \multicolumn{4}{c|}{512} & \multicolumn{1}{c|}{1024}\\
  \hline
  M\'{a}xima dimensi\'{o}n Z de un bloque & \multicolumn{5}{c|}{64}\\
  \hline
  Tama\~{n}o del Warp & \multicolumn{5}{c|}{32}\\
  \hline
  M\'{a}ximo n\'{u}mero de Warps por multiprocesador & \multicolumn{2}{c|}{24} & \multicolumn{2}{c|}{32} & \multicolumn{1}{c|}{48}\\
  \hline
  M\'{a}ximo n\'{u}mero de bloques por multiprocesador & \multicolumn{5}{c|}{8}\\
  \hline
  M\'{a}ximo n\'{u}mero de instrucciones por kernel & \multicolumn{5}{c|}{2 millones}\\
  \hline
\end{tabular}
\caption{Fuente Nvidia}
\end{center}
\end{table}

\subsubsection{M\'{e}todos de descomposici\'{o}n.}
  Los m\'{e}todos de descomposici\'{o}n se encuentran en tres grandes categor\'{\i}as, 
los generales, los espec\'{\i}ficos y los m\'{e}todos mixto o h\'{\i}bridos. 
A continuaci\'{o}n se presentan una breve explicaci\'{o}n de estos m\'{e}todos.

\paragraph{M\'{e}todos Generales.}

\subparagraph{Descomposici\'{o}n de Dominio.}
  Este se utiliza cuando es posible resolver un problema aplicando la misma operaci\'{o}n sobre partes diferentes de su dominio de datos, 
vale decir, es apropiado para algoritmos que trabajan con una gran cantidad de informaci\'{o}n, 
en los que la disyuntiva viene dada por el volumen, sus faces son las siguientes:
  \par
  \begin{itemize}
    \item Se trocean los datos de forma homog\'{e}nea para obtener particiones del dominio original.
    \item Se estudia c\'{o}mo asociar computaci\'{o}n a cada subdominio de datos.
    \item Se asocia la gesti\'{o}n de cada partici\'{o}n a una tarea que contendr\'{a} los datos y un conjunto de operaciones sobre dichos datos.
  \end{itemize}
  \par
  En tanto que los datos a descomponer son los que se muestran a continuaci\'{o}n:
  \par
  \begin{itemize}
    \item Datos de salida: Cada componente de los datos de salida se puede calcular de forma independiente del resto.
    \item Datos de entrada.
    \item Datos intermedios: es posible a veces obtener un mayor grado de concurrencia centr\'{a}ndose en datos intermedios entre etapas.
  \end{itemize}
  \par

\subparagraph{Descomposici\'{o}n funcional dirigida por el flujo de datos}
  Este m\'{e}todo de descomposici\'{o}n se ajusta a la propia arquitectura de la aplicaci\'{o}n a paralelizar. Siendo sus pasos los siguientes:
  \par
  \begin{itemize}
    \item Se identifican las partes funcionales del c\'{a}lculo.
    \item Se asigna una tarea para la realizaci\'{o}n de cada fase identificada.
    \item Se examinan los requisitos de datos de dichas tareas.
      \subitem  Superposici\'{o}n de datos m\'{\i}nima y volumen de flujo de datos peque\~{n}o.
      \subitem  Excesivo solapamiento de datos.
  \end{itemize}
  \par

\subparagraph{Descomposici\'{o}n recursiva.}
  Este m\'{e}todo de descomposici\'{o}n es apropiado para problemas resolubles mediante la t\'{e}cnica Divide-y-vencer\'{a}s.
Cada uno de los subproblemas generados en el proceso de divisi\'{o}n se corresponde con un proceso.
  \par
  Para nuestro caso en particular este m\'{e}todo no es una opci\'{o}n, 
dado que en las arquitectura de las tarjetas de video Nvidia CUDA no es posibile de efectuar recursividad.
  \par

\paragraph{M\'{e}todos Espec\'{\i}ficos.}

\subparagraph{Descomposici\'{o}n exploratoria.}
  Este m\'{e}todo es apropiado para descomponer c\'{a}lculos basados en la b\'{u}squeda de un espacio de soluciones.
Lo malo es que puede resultar en un speed-up an\'{o}malo,
ya que dependiendo de donde se encuentra la soluci\'{o}n dentro del espacio exploratorio,
la soluci\'{o}n paralela puede requerir mas trabajo que la formulaci\'{o}n secuencial.

\par
\begin{center}
\includegraphics[height=7cm,width=15cm]{imgSalida/arbol.eps}
\end{center}
\par

\subparagraph{Descomposici\'{o}n especulativa.}
  Este m\'{e}todo de descomposici\'{o}n es esado para extraer concurrencia en problemas donde el pr\'{o}ximo paso es una acci\'{o}n (entre varias posibles),
que s\'{o}lo se puede determinar cuando la tarea actual concluya.
El m\'{e}todo asume un cierto resultado de la tarea actual y ejecuta los pasos posteriores, si la predicci\'{o}n es err\'{o}nea,
el trabajo realizado se desperdicia y en algunos casos puede que haya que deshacer los resultados de la tarea (restauraci\'{o}n de contexto).

\paragraph{M\'{e}todos mixtos o h\'{\i}bridos.}
   Este tipo de m\'{e}todo de descomposici\'{o}n utiliza una mezcla de los esquemas de descomposici\'{o}n anteriormente descritos,
en diferentes medidas de acuerdo al procesamiento de cada aplicaci\'{o}n.
Algunos ejemplos son los que se presentan a continuaci\'{o}n:
  \par
  \begin{itemize}
    \item Evaluaci\'{o}n polinomial m\'{\i}nima: Evaluaci\'{o}n (descomposici\'{o}n del dominio) y el calculo del m\'{\i}nimo (descomposici\'{o}n del recursiva).
    \item Producto escalar: Evaluaci\'{o}n sumas parciales (descomposici\'{o}n del dominio) y la suma de t\'{e}rminos locales (descomposici\'{o}n del recursiva).
  \end{itemize}

\subsection{Asignaci\'{o}n}
  La encrucijada que nace es saber la necesidad de la correcta asignaci\'{o}n de las tareas,
y no es un tema trivial a la hora de realizar programas que trabajen en conjunto de manera concurrente,
la asignaci\'{o}n de tareas de forma aleatoria no es nada \'{o}ptima,
este es un aspecto critico a fin de minimizar el costo computacional asociado al paralelismo,
y es que las causas m\'{a}s comunes de este costo est\'{a}n asociadas con la comunicaci\'{o}n entre los procesos,
y la carga de trabajo no equilibrada, siendo esta ultima la mayormente significativa.
El equilibrado de carga es fundamental para maximizar la concurrencia,
pero una asignaci\'{o}n equitativa de tareas no garantiza el equilibrado de carga,
ya que esto depende de las homogeneidad de de la arquitectura.
\par
  El objetivo fundamental de la asignaci\'{o}n de taraes es el de minimizar tiempo de ejecuci\'{o}n total.
Para esto se a prever la correcta correspondencia tareas-procesos, 
el agrupamiento previo de algunas tareas dependientes en una sola y la selecci\'{o}n de un orden de ejecuci\'{o}n para las mismas, 
como los pilares fundamentales para fundar la soluci\'{o}n.
  \par
  Las principales estrategias que se han de optar son:
  \par
  \begin{itemize}
    \item Maximizar la concurrencia, asignando las tareas independientes a diferentes procesos.
    \item Asignando tareas que interact\'{u}en mucho al mismo proceso.
    \item Evitar fuentes de ociosidad, como lo puede ser el desequilibrio de la carga \'{o} la espera entre procesos debida a dependencias entre tareas.
  \end{itemize}
  \par
  La imagen a continuaci\'{o}n muestra un \'{a}rbol de tareas junto con los pasos que cada una de estas requiere, 
y las dependencias que entre estas existen.
\par
\begin{center}
\includegraphics[height=9cm,width=10cm]{imgSalida/arboldedependencias.eps}
\end{center}
\par
En la imagen a continuaci\'{o}n se ejemplifica el problema de la ociosidad producida por la dependencia de las tareas,
al utilizar solo dos procesos trabajando en paralelo.
\par
\begin{center}
\includegraphics[height=4cm,width=10cm]{imgSalida/pasos.eps}
\end{center}
\par
  Una mejor soluci\'{o}n para este mismo problema puede ser la que se muestra en la imagen siguiente,
en la que que se reduce la cantidad de pasos necesarios de 16 a 13,
y si bien la soluci\'{o}n no es mucho mejor que la anterior, lo importante es el concepto que hay por detr\'{a}s, 
en la que con el simple echo de una buena asignaci\'{o}n se reduce el tiempo total.
\par
\begin{center}
\includegraphics[height=4cm,width=10cm]{imgSalida/pasos1.eps}
\end{center}
\par

\subsubsection{T\'{e}cnicas de equilibrado de carga.}
  Dos son las t\'{e}cnicas que se pueden utilizar para procurar equilibrar la carga y minimizar el costo computacional,
las cuales difieren en la dinamicidad con la que se trata la carga computacional, vale decir, las Est\'{a}ticas,
como su nombre lo dice no cambia, en tanto que en las Din\'{a}micas, 
estas se modifican durante la ejecuci\'{o}n dependiendo de los requerimientos del momento.

\paragraph{T\'{e}cnicas Est\'{a}ticas de equilibrado de carga.}
  Como su nombre lo dice son t\'{e}cnicas que no var\'{\i}an a lo largo de la ejecuci\'{o}n del programa,
la configuraci\'{o}n de la distribuci\'{o}n de las cargas es realizada ya sea durante la compilaci\'{o}n del programa
\'{o} mediante programaci\'{o}n inherente al c\'{o}digo, es decir, al escribir el c\'{o}digo.
  \par
  Las tareas se distribuyen entre las unidades de procedimiento antes de comenzar la ejecuci\'{o}n.
Esta t\'{e}cnica es generalmente aplicada a situaciones en donde se conocen las tareas, 
estas son generadas est\'{a}ticamente y los requisitos computacionales son conocidos.
  \par
  Esta t\'{o}cnica es apropiada para algoritmos en los que se usa la descomposici\'{o}n de los datos
\'{o} en los cuales esta puede ser almacenada en forma de arreglo. Dentro de esta podemos mencionar algoritmos:
  \par
  \begin{itemize}
    \item Distribuci\'{o}n en bloque.
    \item Distribuci\'{o}n c\'{\i}clica.
    \item Distribuci\'{o}n c\'{\i}clica en en bloque.
    \item Distribuci\'{o}n aleatoria en bloque.
  \end{itemize}
  \par

\paragraph{T\'{e}cnicas Din\'{a}micas de equilibrado de carga.}
  La diferencia de las t\'{e}cnicas est\'{a}ticas de las t\'{e}cnicas din\'{a}micas,
es que estas cambian durante el tiempo que dure la ejecuci\'{o}n del programa.
  \par
  Las tareas se distribuyen entre los procesadores en tiempo de ejecuci\'{o}n.
Esta t\'{e}cnica es aplicable en situaciones dondes las tareas son generadas din\'{a}micamente por los procesos,
en donde los requisitos computacional son desconocidos.
  \par
  En esta tenemos dos patrones importantes que se deben discutir, los patrones centralizados y los patrones distribuidos,
estos nos hablan del manejo de la carga computacional, en el primer caso,
la carga es distribuida y manejada por una sola unidad de procedimiento (maestro),
la cual se encarga de repartirla a las dem\'{a}s unidades, que en este caso pasan a ser esclavas,
en tanto que los patrones distribuidos,
el trabajo se puede distribuir entre cualquier par de unidades de procedimiento.
En nuestro caso particular,
de ser necesario el uso de una t\'{e}cnica din\'{a}mica de equilibrado de carga lo mas \'{o}ptimo dada la arquitectura ser\'{\i}a, 
utilizar un patr\'{o}n centralizado, en donde la unidad de procedimiento central \'{o} CPU, 
pasar\'{\i}a a ser el maestro y la unidad de procesamiento gr\'{a}fico \'{o} GPU, 
junto con todas sus unidades de procedimiento internas, pasar\'{\i}an a ser los esclavos.

\subsection{Estudio de casos pr\'{a}cticos}
  

\section{Metodolog\'{\i}a de desarrollo}

\subsection{Herremientas}

\subsubsection{C Runtime API}
\subsubsection{CUDA Runtime API}

\section{Resumen}

\bibliography{refs}
\end{document}

